{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".: A\n",
      "   L: B\n",
      "      L: D\n",
      "      R: E\n",
      "   R: C\n",
      "      R: F\n"
     ]
    }
   ],
   "source": [
    "# 定义节点类\n",
    "class TreeNode:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "# 创建节点\n",
    "root = TreeNode('A')\n",
    "root.left = TreeNode('B')\n",
    "root.right = TreeNode('C')\n",
    "root.left.left = TreeNode('D')\n",
    "root.left.right = TreeNode('E')\n",
    "root.right.right = TreeNode('F')\n",
    "\n",
    "# 打印二叉树\n",
    "def print_tree(node, level=0, label=\".\"):\n",
    "    indent = \"   \" * level\n",
    "    print(f\"{indent}{label}: {node.value}\")\n",
    "    if node.left:\n",
    "        print_tree(node.left, level + 1, \"L\")\n",
    "    if node.right:\n",
    "        print_tree(node.right, level + 1, \"R\")\n",
    "\n",
    "print_tree(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node keys: [10, 25]\n",
      "  Node keys: [5, 6]\n",
      "  Node keys: [15, 20]\n",
      "  Node keys: [30, 35, 40]\n"
     ]
    }
   ],
   "source": [
    "class BTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # 最小度数\n",
    "        self.leaf = leaf  # 是否是叶子节点\n",
    "        self.keys = []  # 存储键\n",
    "        self.children = []  # 存储子节点\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self, t):\n",
    "        self.root = BTreeNode(t, True)\n",
    "        self.t = t  # 最小度数\n",
    "\n",
    "    def traverse(self, node, level=0):\n",
    "        if node:\n",
    "            print(f\"{'  ' * level}Node keys: {node.keys}\")\n",
    "            if not node.leaf:\n",
    "                for child in node.children:\n",
    "                    self.traverse(child, level + 1)\n",
    "\n",
    "    def insert(self, key):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2 * self.t - 1):\n",
    "            new_root = BTreeNode(self.t, False)\n",
    "            new_root.children.append(self.root)\n",
    "            self.split_child(new_root, 0)\n",
    "            self.root = new_root\n",
    "\n",
    "        self.insert_non_full(self.root, key)\n",
    "\n",
    "    def insert_non_full(self, node, key):\n",
    "        i = len(node.keys) - 1\n",
    "        if node.leaf:\n",
    "            node.keys.append(None)\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = key\n",
    "        else:\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(node.children[i].keys) == (2 * self.t - 1):\n",
    "                self.split_child(node, i)\n",
    "                if key > node.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(node.children[i], key)\n",
    "\n",
    "    def split_child(self, parent, index):\n",
    "        t = self.t\n",
    "        node = parent.children[index]\n",
    "        new_node = BTreeNode(t, node.leaf)\n",
    "        parent.children.insert(index + 1, new_node)\n",
    "        parent.keys.insert(index, node.keys[t - 1])\n",
    "        new_node.keys = node.keys[t:(2 * t - 1)]\n",
    "        node.keys = node.keys[0:(t - 1)]\n",
    "\n",
    "        if not node.leaf:\n",
    "            new_node.children = node.children[t:(2 * t)]\n",
    "            node.children = node.children[0:t]\n",
    "\n",
    "# 创建 B 树并插入初始键\n",
    "b_tree = BTree(3)\n",
    "initial_keys = [10, 20, 5, 6, 15, 30, 25, 35]\n",
    "\n",
    "for key in initial_keys:\n",
    "    b_tree.insert(key)\n",
    "\n",
    "# 插入新的键\n",
    "insert_key = 40\n",
    "b_tree.insert(insert_key)\n",
    "\n",
    "# 遍历并打印 B 树的结构\n",
    "b_tree.traverse(b_tree.root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree before deletion:\n",
      " `- Node(10, 20)\n",
      "    |- Node(5, 6)\n",
      "    |- Node(15)\n",
      "    `- Node(25, 30, 35)\n",
      "\n",
      "Tree after deletion of 20:\n",
      " `- Node(10, 25)\n",
      "    |- Node(5, 6)\n",
      "    |- Node(15)\n",
      "    `- Node(30, 35)\n"
     ]
    }
   ],
   "source": [
    "class BTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # 最小度数\n",
    "        self.leaf = leaf  # 是否是叶子节点\n",
    "        self.keys = []  # 存储键\n",
    "        self.children = []  # 存储子节点\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self, t):\n",
    "        self.root = BTreeNode(t, True)\n",
    "        self.t = t  # 最小度数\n",
    "\n",
    "    def print_tree(self):\n",
    "        self._print_tree(self.root, \"\", True)\n",
    "\n",
    "    def _print_tree(self, node, indent, last):\n",
    "        if node is not None:\n",
    "            print(indent, \"`- \" if last else \"|- \", end=\"\")\n",
    "            print(f\"Node({', '.join(map(str, node.keys))})\")\n",
    "            indent += \"   \" if last else \"|  \"\n",
    "            for i, child in enumerate(node.children):\n",
    "                self._print_tree(child, indent, i == len(node.children) - 1)\n",
    "\n",
    "    def insert(self, key):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2 * self.t - 1):\n",
    "            s = BTreeNode(self.t, False)\n",
    "            self.root = s\n",
    "            s.children.append(root)\n",
    "            self.split_child(s, 0)\n",
    "            self.insert_non_full(s, key)\n",
    "        else:\n",
    "            self.insert_non_full(root, key)\n",
    "\n",
    "    def insert_non_full(self, node, key):\n",
    "        i = len(node.keys) - 1\n",
    "        if node.leaf:\n",
    "            node.keys.append(None)\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = key\n",
    "        else:\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(node.children[i].keys) == (2 * self.t - 1):\n",
    "                self.split_child(node, i)\n",
    "                if key > node.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(node.children[i], key)\n",
    "\n",
    "    def split_child(self, parent, i):\n",
    "        t = self.t\n",
    "        y = parent.children[i]\n",
    "        z = BTreeNode(t, y.leaf)\n",
    "        parent.children.insert(i + 1, z)\n",
    "        parent.keys.insert(i, y.keys[t - 1])\n",
    "        z.keys = y.keys[t:(2 * t - 1)]\n",
    "        y.keys = y.keys[0:(t - 1)]\n",
    "        if not y.leaf:\n",
    "            z.children = y.children[t:(2 * t)]\n",
    "            y.children = y.children[0:t]\n",
    "\n",
    "    def delete(self, key):\n",
    "        root = self.root\n",
    "        if root.leaf:\n",
    "            if key in root.keys:\n",
    "                root.keys.remove(key)\n",
    "            if not root.keys:\n",
    "                self.root = None\n",
    "            return\n",
    "        self.delete_key(root, key)\n",
    "        if len(root.keys) == 0 and not root.leaf:\n",
    "            self.root = root.children[0]\n",
    "\n",
    "    def delete_key(self, node, key):\n",
    "        t = self.t\n",
    "        index = self.find_key(node, key)\n",
    "        if index < len(node.keys) and node.keys[index] == key:\n",
    "            if node.leaf:\n",
    "                node.keys.pop(index)\n",
    "            else:\n",
    "                self.delete_from_non_leaf(node, index)\n",
    "        else:\n",
    "            if node.leaf:\n",
    "                return\n",
    "            flag = (index == len(node.keys))\n",
    "            if len(node.children[index].keys) < t:\n",
    "                self.fill(node, index)\n",
    "            if flag and index > len(node.keys):\n",
    "                self.delete_key(node.children[index - 1], key)\n",
    "            else:\n",
    "                self.delete_key(node.children[index], key)\n",
    "\n",
    "    def delete_from_non_leaf(self, node, index):\n",
    "        t = self.t\n",
    "        key = node.keys[index]\n",
    "        if len(node.children[index].keys) >= t:\n",
    "            pred = self.get_pred(node, index)\n",
    "            node.keys[index] = pred\n",
    "            self.delete_key(node.children[index], pred)\n",
    "        elif len(node.children[index + 1].keys) >= t:\n",
    "            succ = self.get_succ(node, index)\n",
    "            node.keys[index] = succ\n",
    "            self.delete_key(node.children[index + 1], succ)\n",
    "        else:\n",
    "            self.merge(node, index)\n",
    "            self.delete_key(node.children[index], key)\n",
    "\n",
    "    def get_pred(self, node, index):\n",
    "        current = node.children[index]\n",
    "        while not current.leaf:\n",
    "            current = current.children[-1]\n",
    "        return current.keys[-1]\n",
    "\n",
    "    def get_succ(self, node, index):\n",
    "        current = node.children[index + 1]\n",
    "        while not current.leaf:\n",
    "            current = current.children[0]\n",
    "        return current.keys[0]\n",
    "\n",
    "    def fill(self, node, index):\n",
    "        t = self.t\n",
    "        if index != 0 and len(node.children[index - 1].keys) >= t:\n",
    "            self.borrow_from_prev(node, index)\n",
    "        elif index != len(node.keys) and len(node.children[index + 1].keys) >= t:\n",
    "            self.borrow_from_next(node, index)\n",
    "        else:\n",
    "            if index != len(node.keys):\n",
    "                self.merge(node, index)\n",
    "            else:\n",
    "                self.merge(node, index - 1)\n",
    "\n",
    "    def borrow_from_prev(self, node, index):\n",
    "        child = node.children[index]\n",
    "        sibling = node.children[index - 1]\n",
    "        child.keys.insert(0, node.keys[index - 1])\n",
    "        if not child.leaf:\n",
    "            child.children.insert(0, sibling.children.pop())\n",
    "        node.keys[index - 1] = sibling.keys.pop()\n",
    "\n",
    "    def borrow_from_next(self, node, index):\n",
    "        child = node.children[index]\n",
    "        sibling = node.children[index + 1]\n",
    "        child.keys.append(node.keys[index])\n",
    "        if not child.leaf:\n",
    "            child.children.append(sibling.children.pop(0))\n",
    "        node.keys[index] = sibling.keys.pop(0)\n",
    "\n",
    "    def merge(self, node, index):\n",
    "        t = self.t\n",
    "        child = node.children[index]\n",
    "        sibling = node.children[index + 1]\n",
    "        child.keys.append(node.keys[index])\n",
    "        child.keys.extend(sibling.keys)\n",
    "        if not child.leaf:\n",
    "            child.children.extend(sibling.children)\n",
    "        node.keys.pop(index)\n",
    "        node.children.pop(index + 1)\n",
    "\n",
    "    def find_key(self, node, key):\n",
    "        i = 0\n",
    "        while i < len(node.keys) and key > node.keys[i]:\n",
    "            i += 1\n",
    "        return i\n",
    "\n",
    "def main():\n",
    "    # 创建 B 树\n",
    "    t = 2\n",
    "    btree = BTree(t)\n",
    "\n",
    "    # 插入键\n",
    "    keys_to_insert = [10, 20, 5, 6, 15, 30, 25, 35]\n",
    "    for key in keys_to_insert:\n",
    "        btree.insert(key)\n",
    "\n",
    "    # 打印树结构\n",
    "    print(\"Tree before deletion:\")\n",
    "    btree.print_tree()\n",
    "\n",
    "    # 删除键（选择一个键进行删除，例如 20）\n",
    "    btree.delete(20)\n",
    "\n",
    "    # 打印树结构\n",
    "    print(\"\\nTree after deletion of 20:\")\n",
    "    btree.print_tree()\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree structure:\n",
      " `- Node(10, 20)\n",
      "    |- Node(5, 6)\n",
      "    |- Node(15)\n",
      "    `- Node(25, 30, 35)\n",
      "\n",
      "Key 15 found in node with keys: [15] at position 0\n",
      "\n",
      "Key 50 not found in the B-Tree\n"
     ]
    }
   ],
   "source": [
    "class BTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # 最小度数\n",
    "        self.leaf = leaf  # 是否是叶子节点\n",
    "        self.keys = []  # 存储键\n",
    "        self.children = []  # 存储子节点\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self, t):\n",
    "        self.root = BTreeNode(t, True)\n",
    "        self.t = t  # 最小度数\n",
    "\n",
    "    def search(self, key):\n",
    "        return self._search(self.root, key)\n",
    "\n",
    "    def _search(self, node, key):\n",
    "        i = 0\n",
    "        while i < len(node.keys) and key > node.keys[i]:\n",
    "            i += 1\n",
    "        if i < len(node.keys) and key == node.keys[i]:\n",
    "            return (node, i)\n",
    "        elif node.leaf:\n",
    "            return None\n",
    "        else:\n",
    "            return self._search(node.children[i], key)\n",
    "\n",
    "    def print_tree(self):\n",
    "        self._print_tree(self.root, \"\", True)\n",
    "\n",
    "    def _print_tree(self, node, indent, last):\n",
    "        if node is not None:\n",
    "            print(indent, \"`- \" if last else \"|- \", end=\"\")\n",
    "            print(f\"Node({', '.join(map(str, node.keys))})\")\n",
    "            indent += \"   \" if last else \"|  \"\n",
    "            for i, child in enumerate(node.children):\n",
    "                self._print_tree(child, indent, i == len(node.children) - 1)\n",
    "\n",
    "    def insert(self, key):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2 * self.t - 1):\n",
    "            s = BTreeNode(self.t, False)\n",
    "            self.root = s\n",
    "            s.children.append(root)\n",
    "            self.split_child(s, 0)\n",
    "            self.insert_non_full(s, key)\n",
    "        else:\n",
    "            self.insert_non_full(root, key)\n",
    "\n",
    "    def insert_non_full(self, node, key):\n",
    "        i = len(node.keys) - 1\n",
    "        if node.leaf:\n",
    "            node.keys.append(None)\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = key\n",
    "        else:\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(node.children[i].keys) == (2 * self.t - 1):\n",
    "                self.split_child(node, i)\n",
    "                if key > node.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(node.children[i], key)\n",
    "\n",
    "    def split_child(self, parent, i):\n",
    "        t = self.t\n",
    "        y = parent.children[i]\n",
    "        z = BTreeNode(t, y.leaf)\n",
    "        parent.children.insert(i + 1, z)\n",
    "        parent.keys.insert(i, y.keys[t - 1])\n",
    "        z.keys = y.keys[t:(2 * t - 1)]\n",
    "        y.keys = y.keys[0:(t - 1)]\n",
    "        if not y.leaf:\n",
    "            z.children = y.children[t:(2 * t)]\n",
    "            y.children = y.children[0:t]\n",
    "\n",
    "    def delete(self, key):\n",
    "        root = self.root\n",
    "        if root.leaf:\n",
    "            if key in root.keys:\n",
    "                root.keys.remove(key)\n",
    "            if not root.keys:\n",
    "                self.root = None\n",
    "            return\n",
    "        self.delete_key(root, key)\n",
    "        if len(root.keys) == 0 and not root.leaf:\n",
    "            self.root = root.children[0]\n",
    "\n",
    "    def delete_key(self, node, key):\n",
    "        t = self.t\n",
    "        index = self.find_key(node, key)\n",
    "        if index < len(node.keys) and node.keys[index] == key:\n",
    "            if node.leaf:\n",
    "                node.keys.pop(index)\n",
    "            else:\n",
    "                self.delete_from_non_leaf(node, index)\n",
    "        else:\n",
    "            if node.leaf:\n",
    "                return\n",
    "            flag = (index == len(node.keys))\n",
    "            if len(node.children[index].keys) < t:\n",
    "                self.fill(node, index)\n",
    "            if flag and index > len(node.keys):\n",
    "                self.delete_key(node.children[index - 1], key)\n",
    "            else:\n",
    "                self.delete_key(node.children[index], key)\n",
    "\n",
    "    def delete_from_non_leaf(self, node, index):\n",
    "        t = self.t\n",
    "        key = node.keys[index]\n",
    "        if len(node.children[index].keys) >= t:\n",
    "            pred = self.get_pred(node, index)\n",
    "            node.keys[index] = pred\n",
    "            self.delete_key(node.children[index], pred)\n",
    "        elif len(node.children[index + 1].keys) >= t:\n",
    "            succ = self.get_succ(node, index)\n",
    "            node.keys[index] = succ\n",
    "            self.delete_key(node.children[index + 1], succ)\n",
    "        else:\n",
    "            self.merge(node, index)\n",
    "            self.delete_key(node.children[index], key)\n",
    "\n",
    "    def get_pred(self, node, index):\n",
    "        current = node.children[index]\n",
    "        while not current.leaf:\n",
    "            current = current.children[-1]\n",
    "        return current.keys[-1]\n",
    "\n",
    "    def get_succ(self, node, index):\n",
    "        current = node.children[index + 1]\n",
    "        while not current.leaf:\n",
    "            current = current.children[0]\n",
    "        return current.keys[0]\n",
    "\n",
    "    def fill(self, node, index):\n",
    "        t = self.t\n",
    "        if index != 0 and len(node.children[index - 1].keys) >= t:\n",
    "            self.borrow_from_prev(node, index)\n",
    "        elif index != len(node.keys) and len(node.children[index + 1].keys) >= t:\n",
    "            self.borrow_from_next(node, index)\n",
    "        else:\n",
    "            if index != len(node.keys):\n",
    "                self.merge(node, index)\n",
    "            else:\n",
    "                self.merge(node, index - 1)\n",
    "\n",
    "    def borrow_from_prev(self, node, index):\n",
    "        child = node.children[index]\n",
    "        sibling = node.children[index - 1]\n",
    "        child.keys.insert(0, node.keys[index - 1])\n",
    "        if not child.leaf:\n",
    "            child.children.insert(0, sibling.children.pop())\n",
    "        node.keys[index - 1] = sibling.keys.pop()\n",
    "\n",
    "    def borrow_from_next(self, node, index):\n",
    "        child = node.children[index]\n",
    "        sibling = node.children[index + 1]\n",
    "        child.keys.append(node.keys[index])\n",
    "        if not child.leaf:\n",
    "            child.children.append(sibling.children.pop(0))\n",
    "        node.keys[index] = sibling.keys.pop(0)\n",
    "\n",
    "    def merge(self, node, index):\n",
    "        t = self.t\n",
    "        child = node.children[index]\n",
    "        sibling = node.children[index + 1]\n",
    "        child.keys.append(node.keys[index])\n",
    "        child.keys.extend(sibling.keys)\n",
    "        if not child.leaf:\n",
    "            child.children.extend(sibling.children)\n",
    "        node.keys.pop(index)\n",
    "        node.children.pop(index + 1)\n",
    "\n",
    "    def find_key(self, node, key):\n",
    "        i = 0\n",
    "        while i < len(node.keys) and key > node.keys[i]:\n",
    "            i += 1\n",
    "        return i\n",
    "\n",
    "def main():\n",
    "    # 创建 B 树\n",
    "    t = 2\n",
    "    btree = BTree(t)\n",
    "\n",
    "    # 插入键\n",
    "    keys_to_insert = [10, 20, 5, 6, 15, 30, 25, 35]\n",
    "    for key in keys_to_insert:\n",
    "        btree.insert(key)\n",
    "\n",
    "    # 打印树结构\n",
    "    print(\"Tree structure:\")\n",
    "    btree.print_tree()\n",
    "\n",
    "    # 搜索键（选择一个键进行搜索，例如 15 和 50）\n",
    "    search_keys = [15, 50]\n",
    "    for key in search_keys:\n",
    "        result = btree.search(key)\n",
    "        if result:\n",
    "            print(f\"\\nKey {key} found in node with keys: {result[0].keys} at position {result[1]}\")\n",
    "        else:\n",
    "            print(f\"\\nKey {key} not found in the B-Tree\")\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Root Internal Node: [102]\n",
      "  Child 0 Leaf Node: [101]\n",
      "  Child 1 Leaf Node: [103, 104, 105]\n"
     ]
    }
   ],
   "source": [
    "class BPlusTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # 阶数\n",
    "        self.leaf = leaf  # 是否是叶子节点\n",
    "        self.keys = []  # 存储键\n",
    "        self.children = []  # 存储子节点\n",
    "        self.next = None  # 指向下一个叶子节点的指针\n",
    "\n",
    "class BPlusTree:\n",
    "    def __init__(self, t):\n",
    "        self.root = BPlusTreeNode(t, True)  # 初始化一个空树\n",
    "        self.t = t\n",
    "\n",
    "    def insert(self, key):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2 * self.t - 1):  # 根节点满了\n",
    "            s = BPlusTreeNode(self.t, False)  # 新的根节点\n",
    "            self.root = s\n",
    "            s.children.append(root)\n",
    "            self.split_child(s, 0)\n",
    "            self.insert_non_full(s, key)\n",
    "        else:\n",
    "            self.insert_non_full(root, key)\n",
    "\n",
    "    def insert_non_full(self, node, key):\n",
    "        if node.leaf:\n",
    "            node.keys.append(None)  # 为新键腾出空间\n",
    "            i = len(node.keys) - 2\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = key\n",
    "            node.keys.sort()\n",
    "        else:\n",
    "            i = len(node.keys) - 1\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(node.children[i].keys) == (2 * self.t - 1):\n",
    "                self.split_child(node, i)\n",
    "                if key > node.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(node.children[i], key)\n",
    "\n",
    "    def split_child(self, parent, i):\n",
    "        t = self.t\n",
    "        node = parent.children[i]\n",
    "        new_node = BPlusTreeNode(t, node.leaf)\n",
    "        parent.children.insert(i + 1, new_node)\n",
    "        parent.keys.insert(i, node.keys[t - 1])\n",
    "        new_node.keys = node.keys[t:]\n",
    "        node.keys = node.keys[:t - 1]\n",
    "        if not node.leaf:\n",
    "            new_node.children = node.children[t:]\n",
    "            node.children = node.children[:t]\n",
    "\n",
    "        if node.leaf:\n",
    "            new_node.next = node.next\n",
    "            node.next = new_node\n",
    "\n",
    "    def display(self, node=None, level=0, pos='Root'):\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        indent = \"  \" * level\n",
    "        if node.leaf:\n",
    "            print(f\"{indent}{pos} Leaf Node: {node.keys}\")\n",
    "        else:\n",
    "            print(f\"{indent}{pos} Internal Node: {node.keys}\")\n",
    "            for i, child in enumerate(node.children):\n",
    "                self.display(child, level + 1, pos=f'Child {i}')\n",
    "\n",
    "# Example usage:\n",
    "bpt = BPlusTree(t=2)\n",
    "keys = [101, 102, 103, 104, 105]\n",
    "\n",
    "for key in keys:\n",
    "    bpt.insert(key)\n",
    "\n",
    "bpt.display()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B 树 查找时间: 0.000000 秒\n",
      "B+ 树 查找时间: 0.000000 秒\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "import random\n",
    "\n",
    "# B树节点类\n",
    "class BTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # 阶数\n",
    "        self.leaf = leaf  # 是否是叶子节点\n",
    "        self.keys = []  # 存储键\n",
    "        self.children = []  # 存储子节点\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self, t):\n",
    "        self.root = BTreeNode(t, True)  # 初始化一个空树\n",
    "        self.t = t\n",
    "\n",
    "    def search(self, key, node=None):\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        i = 0\n",
    "        while i < len(node.keys) and key > node.keys[i]:\n",
    "            i += 1\n",
    "        if i < len(node.keys) and key == node.keys[i]:\n",
    "            return True\n",
    "        if node.leaf:\n",
    "            return False\n",
    "        return self.search(key, node.children[i])\n",
    "\n",
    "    def insert(self, key):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2 * self.t - 1):  # 根节点满了\n",
    "            s = BTreeNode(self.t, False)  # 新的根节点\n",
    "            self.root = s\n",
    "            s.children.append(root)\n",
    "            self.split_child(s, 0)\n",
    "            self.insert_non_full(s, key)\n",
    "        else:\n",
    "            self.insert_non_full(root, key)\n",
    "\n",
    "    def insert_non_full(self, node, key):\n",
    "        if node.leaf:\n",
    "            node.keys.append(None)  # 为新键腾出空间\n",
    "            i = len(node.keys) - 2\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = key\n",
    "        else:\n",
    "            i = len(node.keys) - 1\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(node.children[i].keys) == (2 * self.t - 1):\n",
    "                self.split_child(node, i)\n",
    "                if key > node.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(node.children[i], key)\n",
    "\n",
    "    def split_child(self, parent, i):\n",
    "        t = self.t\n",
    "        node = parent.children[i]\n",
    "        new_node = BTreeNode(t, node.leaf)\n",
    "        parent.children.insert(i + 1, new_node)\n",
    "        parent.keys.insert(i, node.keys[t - 1])\n",
    "        new_node.keys = node.keys[t:]\n",
    "        node.keys = node.keys[:t - 1]\n",
    "        if not node.leaf:\n",
    "            new_node.children = node.children[t:]\n",
    "            node.children = node.children[:t]\n",
    "\n",
    "# B+树节点类\n",
    "class BPlusTreeNode:\n",
    "    def __init__(self, t, leaf=False):\n",
    "        self.t = t  # 阶数\n",
    "        self.leaf = leaf  # 是否是叶子节点\n",
    "        self.keys = []  # 存储键\n",
    "        self.children = []  # 存储子节点\n",
    "        self.next = None  # 指向下一个叶子节点的指针\n",
    "\n",
    "class BPlusTree:\n",
    "    def __init__(self, t):\n",
    "        self.root = BPlusTreeNode(t, True)  # 初始化一个空树\n",
    "        self.t = t\n",
    "\n",
    "    def search(self, key, node=None):\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        while node:\n",
    "            i = 0\n",
    "            while i < len(node.keys) and key > node.keys[i]:\n",
    "                i += 1\n",
    "            if i < len(node.keys) and key == node.keys[i]:\n",
    "                return True\n",
    "            if node.leaf:\n",
    "                return False\n",
    "            node = node.children[i]\n",
    "        return False\n",
    "\n",
    "    def insert(self, key):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2 * self.t - 1):  # 根节点满了\n",
    "            s = BPlusTreeNode(self.t, False)  # 新的根节点\n",
    "            self.root = s\n",
    "            s.children.append(root)\n",
    "            self.split_child(s, 0)\n",
    "            self.insert_non_full(s, key)\n",
    "        else:\n",
    "            self.insert_non_full(root, key)\n",
    "\n",
    "    def insert_non_full(self, node, key):\n",
    "        if node.leaf:\n",
    "            node.keys.append(None)  # 为新键腾出空间\n",
    "            i = len(node.keys) - 2\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                node.keys[i + 1] = node.keys[i]\n",
    "                i -= 1\n",
    "            node.keys[i + 1] = key\n",
    "            node.keys.sort()\n",
    "        else:\n",
    "            i = len(node.keys) - 1\n",
    "            while i >= 0 and key < node.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(node.children[i].keys) == (2 * self.t - 1):\n",
    "                self.split_child(node, i)\n",
    "                if key > node.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(node.children[i], key)\n",
    "\n",
    "    def split_child(self, parent, i):\n",
    "        t = self.t\n",
    "        node = parent.children[i]\n",
    "        new_node = BPlusTreeNode(t, node.leaf)\n",
    "        parent.children.insert(i + 1, new_node)\n",
    "        parent.keys.insert(i, node.keys[t - 1])\n",
    "        new_node.keys = node.keys[t:]\n",
    "        node.keys = node.keys[:t - 1]\n",
    "        if not node.leaf:\n",
    "            new_node.children = node.children[t:]\n",
    "            node.children = node.children[:t]\n",
    "\n",
    "        if node.leaf:\n",
    "            new_node.next = node.next\n",
    "            node.next = new_node\n",
    "\n",
    "# 测试代码\n",
    "def measure_search_time(tree, keys, search_key):\n",
    "    start_time = time.time()\n",
    "    tree.search(search_key)\n",
    "    end_time = time.time()\n",
    "    search_time = end_time - start_time\n",
    "    return search_time\n",
    "\n",
    "# 创建 B 树 和 B+ 树\n",
    "b_tree = BTree(t=2)\n",
    "b_plus_tree = BPlusTree(t=2)\n",
    "\n",
    "# 生成10000个随机数据\n",
    "keys = random.sample(range(1, 20001), 10000)\n",
    "\n",
    "# 插入相同的数据\n",
    "for key in keys:\n",
    "    b_tree.insert(key)\n",
    "    b_plus_tree.insert(key)\n",
    "\n",
    "# 测量 B 树 和 B+ 树 的查找时间\n",
    "search_key = keys[random.randint(0, 9999)]  # 随机选择一个查找的键\n",
    "b_tree_time = measure_search_time(b_tree, keys, search_key)\n",
    "b_plus_tree_time = measure_search_time(b_plus_tree, keys, search_key)\n",
    "\n",
    "print(f\"B 树 查找时间: {b_tree_time:.6f} 秒\")\n",
    "print(f\"B+ 树 查找时间: {b_plus_tree_time:.6f} 秒\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
